package experiment7;

import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;

public class Assignment {
    static int[][] cost = {
            {9, 2, 7, 8},
            {6, 4, 3, 7},
            {5, 8, 1, 8},
            {7, 6, 9, 4}
    };
    static int infinity = 9 + 7 + 8 + 9;
    static int bestSoFar = 9 + 7 + 8 + 9;

    public static void main(String[] args) {
        PriorityQueue<Node> S = new PriorityQueue<>();

        Node root = new Node();
        root.lowerBound = getLowerBound(root);
        S.add(root);
        while (!S.isEmpty()) {
            Node node = S.remove();
            if (node.lowerBound > bestSoFar) {
                continue;
            }
            for (Node child : allFeasibleChildren(node)) {
                if (isACompleteSolution(child)) {
                    bestSoFar = Math.min(bestSoFar, child.lowerBound);
                } else {
                    S.add(child);
                }
            }
        }
        System.out.println(bestSoFar);
    }

    private static int getLowerBound(Node node) {
        int lb = 0;

        for (int key : node.partialSolution.keySet()) {
            int value = node.partialSolution.get(key);
            lb += cost[key - 1][value];
        }
        for (int i = node.depth + 1; i <= 4; i++) {
            int min = infinity;
            for (int j = 0; j < 4; j++) {
                if (!node.partialSolution.containsValue(j)) {
                    if (cost[i - 1][j] < min) {
                        min = cost[i - 1][j];
                    }
                }
            }
            lb += min;
        }
        return lb;
    }

    private static Iterable<Node> allFeasibleChildren(Node node) {

        int depth = node.depth + 1;
        if (depth > 4) {
            return null;
        }
        List<Node> childList = new ArrayList<>();

        for (int i = 0; i < 4; i++) {
            if (feasible(node, i)) {
                Node child = new Node();
                child.depth = depth;
                child.partialSolution.putAll(node.partialSolution);
                child.partialSolution.put(depth, i);
                child.lowerBound = getLowerBound(child);
                childList.add(child);
            }
        }

        return childList;
    }

    private static boolean isACompleteSolution(Node node) {
        return node.depth == 4;
    }

    private static boolean feasible(Node node, int i) {
        return !node.partialSolution.containsValue(i);
    }
}